package com.techyuan.algorithm.dp;

import com.techyuan.algorithm.utils.PrintUtil;

/**
 * 钢条切割问题
 * 1、为什么可以简化为左边不切割，右边切割?
 * 答：应为若选择左右切割，实际是有一半是重复的。
 * Created by Administrator on 2017/2/15.
 */
public class CutRod {
    static int count = 0;

    public static int cutRod(int[] p, int n) {
        if (n == 0)
            return 0;
        int q = -100;
        for (int i = 0; i < n; i++) {
            q = Math.max(q, p[i] + cutRod(p, n - i - 1));
        }
        count++;
        return q;
    }

    /**
     * 自顶向下，带备忘的动态规划
     * @param p
     * @param r
     * @param n
     * @return
     */
    public static int memCutRod(int[] p, int[] r, int n) {
        if (n == 0)
            return 0;
        if (r[n - 1] > 0) {
            return r[n - 1];
        }
        int q = -100;
        for (int i = 0; i < n; i++) {
            q = Math.max(q, p[i] + memCutRod(p, r, n - i - 1));
        }
        r[n - 1] = q;
        count++;
        return q;
    }

    /**
     * 自底向上
     * @param p
     * @param n
     * @return
     */
    public static int[][] bottomCutRod(int[] p, int n) {
        int[][] r = new int[2][n];
        r[0][0] = p[0];
        r[1][0] = 1;
        for (int i = 1; i < n; i++) {
            r[0][i] = p[i];
            r[1][i] = i + 1;
            for (int j = 0; j < i; j++) {
                if (r[0][i] < p[j] + r[0][i - j - 1]) {
                    r[0][i] = Math.max(r[0][i], p[j] + r[0][i - j - 1]);
                    r[1][i] = j + 1;
                }
            }
        }
        return r;
    }

    public static void main(String[] args) {
        int[] pArr = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
        int n = 9;
        count = 0;
        System.out.println("结果：" + cutRod(pArr, n) + " 递归次数:" + count);
        count = 0;
        System.out.println("结果：" + memCutRod(pArr, new int[n], n) + " 递归次数:" + count);

        int[][] r = bottomCutRod(pArr, n);
        System.out.println("结果：" + r[0][n - 1] + " 递归次数:" + 1);
        System.out.print("切割方案:");
        int tmp = n;
        do {
            System.out.print(r[1][tmp - 1] + ",");
            tmp = tmp - r[1][tmp - 1];
        } while (tmp > 0 && r[1][tmp - 1] != tmp);
        if (tmp > 0)
            System.out.println(r[1][tmp - 1]);
    }
}
